P3224 [HNOI2012]永无乡

发表于

闲扯

找了好久的 $FHQ-Treap$ 的启发式合并，终于找到了，但是题解里面为毛全是 $splay$ 和线段树合并啊。。。

少有的几篇 $FHQ$ 的题解，结果基本都是指针的，只有一片能看。。。

题面

P3224 [HNOI2012]永无乡

Solution

平衡树

因为要查询第 $K$ 大，很容易想到平衡树。

但是连边的操作相当于是合并两个平衡树，所以我们需要一个高效的合并方式——启发式合并。

我们每次暴力的将较小的平衡树中的节点加入到较大的平衡树种，可以证明时间复杂度是 $O(n\log^2 n)$ 的。

每次连边时，先找到每个点所属的平衡树的编号，如果两个点已经在同一个平衡树里面，就忽略掉；否则，判断大小之后，合并即可。

动态开点权值线段树+线段树合并

对每个点建一颗动态开点的权值线段树，用并查集维护点与点之间的连通性。

合并时如果不在一个连通块里面，就合并两个线段树。

注意合并时，如果在并查集中将 $x$ 的父节点指向 $y$ ，那么，合并时也要 $x$ 所在的线段树合并进 $y$ 。

Code

平衡树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x%mod;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res%mod;
}
const int MAXN = 1e5+5;
int n,m,q,ch[MAXN][2],val[MAXN],rd[MAXN],sz[MAXN],id[MAXN],rt[MAXN],u,v,x,y,z;
char opt[2];
it find(int x){return x==rt[x]?x:rt[x]=find(rt[x]);}
#define lc(cur) ch[cur][0]
#define rc(cur) ch[cur][1]
il pushup(int cur){sz[cur]=sz[lc(cur)]+sz[rc(cur)]+1;}
it merge(int x,int y){
	if(!x||!y) return x+y;
	if(rd[x]<rd[y]){
		rc(x)=merge(rc(x),y);
		pushup(x);return x;
	}
	else{
		lc(y)=merge(x,lc(y));
		pushup(y);return y;
	}
}
il split(int cur,int k,int &x,int &y){
	if(!cur) x=y=0;
	else{
		if(val[cur]<=k) x=cur,split(rc(x),k,rc(x),y);
		else y=cur,split(lc(y),k,x,lc(y));
		pushup(cur);
	}
}
it kth(int cur,int k){
	while(1){
		if(sz[lc(cur)]>=k) cur=lc(cur);
		else if(sz[lc(cur)]+1==k) return cur;
		else k-=sz[lc(cur)]+1,cur=rc(cur);
	}
}
il DFS(int a,int &b){
	if(!a) return ;
	DFS(lc(a),b),DFS(rc(a),b);
	lc(a)=rc(a)=0;
	split(b,val[a],x,y);
	b=merge(merge(x,a),y);
}
it Merge(int a,int b){
	if(sz[a]>sz[b]) swap(a,b);
	DFS(a,b);return b;
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(n),read(m);
	for(ri i=1;i<=n;++i) read(val[i]),id[val[i]]=i,rt[i]=i,sz[i]=1,rd[i]=rand();
	for(ri i=1;i<=m;++i){
		read(u),read(v);
		if(find(u)==find(v)) continue;
		z=Merge(find(u),find(v));
		rt[find(u)]=rt[find(v)]=rt[z]=z;
	}
	read(q);
	for(ri i=1;i<=q;++i){
		scanf("%s",opt),read(u),read(v);
		if(opt[0]=='B'){
			if(find(u)==find(v)) continue;
			z=Merge(rt[u],rt[v]);
			rt[find(u)]=rt[find(v)]=rt[z]=z;
		}
		if(opt[0]=='Q'){
			if(sz[find(u)]<v){
				puts("-1");
				continue;
			}
			print(id[val[kth(find(u),v)]]),puts("");
		}
	}
	return 0;
}

线段树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x%mod;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res%mod;
}
const int MAXN = 1e5+5;
int n,m,q,val,u,v,id[MAXN*20],lc[MAXN*20],rc[MAXN*20],sz[MAXN*20],fa[MAXN],rt[MAXN],cnt;
char opt[2];
it find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
il pushup(int cur){sz[cur]=sz[lc[cur]]+sz[rc[cur]];}
il build(int &cur,int l,int r,int pos,int idx){
	if(!cur) cur=++cnt;
	if(l==r){sz[cur]=1,id[cur]=idx;return ;}
	if(mid>=pos) build(lc[cur],l,mid,pos,idx);
	else build(rc[cur],mid+1,r,pos,idx);
	pushup(cur);
}
it merge(int a,int b,int l,int r){
	if(!a||!b) return a+b;
	if(l==r){
		if(id[b]) id[a]=id[b],sz[a]=1;
		return a;
	}
	lc[a]=merge(lc[a],lc[b],l,mid);
	rc[a]=merge(rc[a],rc[b],mid+1,r);
	pushup(a);return a;
}
it query(int cur,int k,int l,int r){
	if(sz[cur]<k||!cur) return 0;
	if(l==r) return id[cur];
	if(k<=sz[lc[cur]]) return query(lc[cur],k,l,mid);
	return query(rc[cur],k-sz[lc[cur]],mid+1,r);
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(n),read(m);
	for(ri i=1;i<=n;++i) read(val),fa[i]=i,build(rt[i],1,n,val,i);
	for(ri i=1;i<=m;++i){
		read(u),read(v);
		u=find(u),v=find(v);
		if(u==v) continue;
		fa[v]=u,rt[u]=merge(rt[u],rt[v],1,n);
	}
	read(q);
	for(ri i=1;i<=q;++i){
		scanf("%s",opt);read(u),read(v);
		if(opt[0]=='B'){
			u=find(u),v=find(v);
			if(u==v) continue;
			fa[v]=u,rt[u]=merge(rt[u],rt[v],1,n);
		}
		if(opt[0]=='Q'){
			u=find(u);
			ri ans=query(rt[u],v,1,n);
			print(!ans?-1:ans),puts("");
		}
	}
	return 0;
}

总结

模板题，要记住，不能忘了。